package demo1;
import java.util.Arrays;

public class DynamicPlanningPractise {
    public int lengthOfLISOther(int[] nums) {
        /**由题可得，递增子序列就是在顺序的条件下一串不连续的递增序列
         状态表示：
         dp[i]表示以i位置为结尾时 最长递增子序列的长度
         我们需要明白，如“9，8，7，6，5”这一个序列，虽然他不递增，但是其每个元素都可以构成一个递增子序列
         即是dp[1],由此我们可以将dp表中所有值填写为1
         状态转移方程：
         分为一种情况，当nums[i]<=nums[i-1]时，此时dp[i]=1;当nums[i]>nums[i-1]时，
         此时构成递增，dp[i] = dp[i-1]+1（长度加1）
         又由上述初始化说明，dp表中已存储其最差时长度，故状态转移方程如下：
         dp[i] += nums[i]>nums[i-1] ? dp[i-1]+1 : 0;
         初始化：
         将整个dp表填充1，从1下标开始遍历
         */
        // int n = nums.length;
        // //1 创建dp表
        // int[] dp = new int[n];
        // //2 初始化
        // Arrays.fill(dp,1);
        // //3 填表
        // for(int i = 1; i < n; i++)
        //     dp[i] += nums[i]>nums[i-1] ? dp[i-1] : 0;
        // //4 返回值
        // int ret = -0x3f3f3f3f;
        // for(int x:dp)
        //     if(x>ret)
        //         ret = x;
        // return ret;

        /**子序列：子序列只需保证其相对位置不变即可
         状态表示：
         dp[i] 表示以i位置为结尾是所有子序列中的最长递增子序列的长度
         状态转移方程：
         dp[i] = nums[i]>nums[j] ? dp[j]+1 ? 1;
         初始化：
         dp[0] = 1 */
        int n = nums.length;
        //1 创建dp表
        int[] dp = new int[n];
        //2 初始化
        dp[0] = 1;
        //3 填表
        for(int i = 1; i < n; i++)
            for(int j = i-1; j >= 0; j--)
                if(nums[i]>nums[j]) {
                    dp[i] = dp[j]+1;//找到第一个后立马退出
                }
                else dp[i] = 1;
        int ret = -0x3f3f3f3f;
        for(int x:dp)
            if(x>ret)
                ret = x;
        return ret;
    }

    /**
     * 优化后的 最长递增子序列
     * 时间复杂度O（n*n）
     * 空间复杂度O（n）*/
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        //1 创建dp表
        int[] dp = new int[n];
        //2 初始化
        Arrays.fill(dp,1);
        //3 填表
        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i-1; j >= 0; j--)
                if(nums[i]>nums[j])
                    dp[i] = dp[j]>=dp[i] ? dp[j]+1 : dp[i];
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }

    /**
     * 摆动序列*/
    public int wiggleMaxLength(int[] nums) {
        /**
         题目给了我一些误导，所谓摆动序列差值一正一负，即是说明元素与元素之间呈起伏
         差值为0时不是摆动序列，也就是说严格起伏，不能出现两个值相等
         状态表示：
         由经验+题目要求可得
         f[i]表示 以i位置元素为结尾的所有子序列中，最后一个元素呈  上升  状态的 最长摆动徐列的长度
         g[i]表示 以i位置元素为结尾的所有子序列中，最后一个元素呈  下降  状态的 最长摆动徐列的长度
         状态转移方程：
         我们一般时通过划分状态的方式推导状态转移方程，如下：
         我们可以将以i下标元素为结尾的所有子序列中的摆动序列分为两种：
         1 长度为1的子序列 --》nums[i]本身
         2 长度大于1的子序列，此时我们需要划分情况，以f[i]为例，
         为了保证是摆动数组，故需要使得nums[i] < nums[j] <j为遍历0~i-1的遍历> -->遍历nums
         为了保证是最长摆动数组，需要执行 dp[i] = Math.max(dp[i],dp[j]+1); -->遍历dp表
         初始化：
         由于仅有一个元素 或者两个不相等的元素也可视作摆动数组，故我们先将dp所有值赋值为1
         后续再行修改--代码哪有一次性全想全的
         */
        int n = nums.length;
        //1 创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        //2 初始化
        Arrays.fill(f,1);
        Arrays.fill(g,1);
        //3 状态转移方程
        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
                /**
                 本来仅有两个不相等的元素时也称之为摆动数组
                 就比如nums = [1,7,4,9,2,5] 这个数组
                 当i==1时，f[i]==2 g[i]是否也需要等于2呢？毕竟这是两个不同的元素
                 大可不必！因为我们状态表示中f[i] g[i]还表示下降和上升这两种状态，故在该状态下，g[i]==1是毫无疑问的 */
                f[i] = nums[i]>nums[j] ? Math.max(f[i],g[j]+1) : f[i];
                ret = ret<f[i] ? f[i] : ret;
                g[i] = nums[i]<nums[j] ? Math.max(g[i],f[j]+1) : g[i];
                ret = ret<g[i] ? g[i] : ret;
            }
        }
        //4 返回值
        return ret;
    }

    /**
     * 摆动数组优化
     * 时间复杂度O（n*n）
     * 空间复杂度O（n）*/
    public int wiggleMaxLengthOther(int[] nums) {
        int n = nums.length;
        //1 创建dp表
        int[] f = new int[n];//上升
        int[] g = new int[n];//下降
        //2 初始化
        Arrays.fill(f,1);
        Arrays.fill(g,1);
        //3 填表
        int ret = 1;
        for(int i = 1; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
                f[i] = nums[i]>nums[j] ? Math.max(f[i],g[j]+1) : f[i];
                g[i] = nums[i]<nums[j] ? Math.max(g[i],f[j]+1) : g[i];
                ret = Math.max(Math.max(f[i],ret),g[i]);
            }
        }
        //4 返回值
        return ret;
    }
}


